import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution30 {
    public List<Integer> findSubstring(String s, String[] words) {
        int len=words.length*words[0].length();
        if (s.length()<len){
            return new ArrayList<>();
        }
        Map<String,Integer> map=new HashMap<>();
        for (String word : words) {
            map.put(word,map.getOrDefault(word,0)+1);
        }
        List<Integer> ans=new ArrayList<>();
        int[] f=new int[26];
        for (String word : words) {
            for (char c : word.toCharArray()) {
                f[c-'a']++;
            }
        }
        int[] g=new int[26];
        for (int i=0;i<len;i++){
            g[s.charAt(i)-'a']++;
        }
        int d=0;
        for (int i=0;i<26;i++){
            if (f[i]!=g[i]){
                d++;
            }
        }
        if (d==0){
            boolean flag=true;
            Map<String,Integer> map1=new HashMap<>(map);
            for (int i=0;i<len;i+=words[0].length()){
                if (map1.getOrDefault(s.substring(i,i+words[0].length()),0)==0){
                    flag=false;
                    break;
                }
                map1.put(s.substring(i,i+words[0].length()),map1.get(s.substring(i,i+words[0].length()))-1);
            }
            if (flag){
                ans.add(0);
            }
        }
        for (int i=len;i<s.length();i++){
            if (g[s.charAt(i-len)-'a']==f[s.charAt(i-len)-'a']){
                d++;
            }
            g[s.charAt(i-len)-'a']--;
            if (g[s.charAt(i-len)-'a']==f[s.charAt(i-len)-'a']){
                d--;
            }
            if (g[s.charAt(i)-'a']==f[s.charAt(i)-'a']){
                d++;
            }
            g[s.charAt(i)-'a']++;
            if (g[s.charAt(i)-'a']==f[s.charAt(i)-'a']){
                d--;
            }
            if (d==0){
                boolean flag=true;
                Map<String,Integer> map1=new HashMap<>(map);
                for (int j=i-len+1;j<=i;j+=words[0].length()){
                    if (map1.getOrDefault(s.substring(j,j+words[0].length()),0)==0){
                        flag=false;
                        break;
                    }
                    map1.put(s.substring(j,j+words[0].length()),map1.get(s.substring(j,j+words[0].length()))-1);
                }
                if (flag) {
                    ans.add(i-len+1);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution30().findSubstring("barfoothefoobarman",new String[]{"foo","bar"}));
    }
}
